package com.txy.alth.dp;

/**
 * 斐波那契数列
 */
public class Fib2 {
    // 用于存储中间计算结果
    static long[] sub = new long[65];

    public static long fib(int n) {
        if(n <= 1) {
            return n;
        }
        if(sub[n]!=0) return sub[n];
        sub[n] = fib(n-1) + fib(n-2);
        return sub[n];
    }

    public static void main(String[] args) {
        System.out.println(fib(64));
    }
}
